<?php
/**
 * @title 93. 复原IP地址 - 递归
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param String $s
     * @return String[]
     */
    function restoreIpAddresses($s) {
        /**
         * @since 2021-09-03 ip集合
         */
        $this->ipArray = [];

        /**
         * @since 2021-09-03 长度
         */
        $this->len = strlen($s);
        $this->s = $s;

        /**
         * @since 2021-09-03 找符合条件的ip
         */
        self::find(0, 4, "");

        /**
         * @return
         */
        return $this->ipArray;
    }

    /**
     * @title 查找符合
     * @author start2004
     * @since 2021-09-03 Created
     *
     * @param int $p
     * @param int $cnt
     * @param string $ips
     * @return void
     */
    public function find($p = 0, $cnt = 0, $ips){
        /**
         * @since 2021-09-03 剩余长度
         */
        $remainLen = $this->len-$p;

        /**
         * @since 2021-09-03 字符长度是否符合条件
         */
        if($remainLen < $cnt OR $remainLen > $cnt*3){
            return ;
        } else {}

        /**
         * @since 2021-09-03 只有1个数字
         */
        if($cnt == 1){
            /**
             * @since 2021-09-03 ip第4位数字
             */
            $num = substr($this->s, $p);

            /**
             * @since 2021-09-03 不能为空, 不能超过255
             */
            if($num > 255){
                return ;
            } else {}

            /**
             * @since 2021-09-03 不能有前导0
             */
            if(strlen($num) > 1 AND $num[0] == "0"){
                return ;
            } else {}

            /**
             * @since 2021-09-03 符合条件
             */
            $this->ipArray[] = $ips . $num;
        } else {
            $cnt--;

            /**
             * @since 2021-09-03 ip的第`5-cnt`位数字, 长度依次1到3
             * @since 2021-09-03 长度1
             */
            $ip = $this->s[$p];
            $p++;
            self::find($p, $cnt, $ips ."{$ip}.");

            /**
             * @since 2021-09-03 长度为2-3, 不能有前导0
             */
            if($ip == "0"){
                return ;
            } else {}

            /**
             * @since 2021-09-03 长度2
             */
            if(isset($this->s[$p])){
                $ip = $ip . $this->s[$p];
                $p++;
                self::find($p, $cnt, $ips ."{$ip}.");
            } else {}
            
            /**
             * @since 2021-09-03 长度3, 不超过255
             */
            if(isset($this->s[$p])){
                $ip = $ip . $this->s[$p];
                $p++;
                if($ip <= 255){
                    self::find($p, $cnt, $ips ."{$ip}.");
                } else {}
            } else {}
        }
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.09_2.php
 */
$datas = [
    "25525511135",
    "010010",
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->restoreIpAddresses($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
